#define _CRT_SECURE_NO_WARNINGS 1

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}


class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
        ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
        dummy->next = A;
        ListNode* slow = dummy;
        ListNode* fast = dummy;
        while (fast->next && fast)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* cur = slow->next;
        ListNode* newhead = slow;
        ListNode* next = cur->next;
        slow->next = NULL;
        while (1)
        {
            cur->next = newhead;
            newhead = cur;
            if (next == NULL)
                break;
            cur = next;
            next = cur->next;
        }
        ListNode* head = A;
        ListNode* tail = cur;

        while (tail != slow)
        {
            if (head->val != tail->val)
                return false;
            head = head->next;
            tail = tail->next;
        }
        return true;
    }
};


struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* head1 = headA;
    struct ListNode* head2 = headB;
    int len1 = 1, len2 = 1;
    while (head1->next)
    {
        len1++;
        head1 = head1->next;
    }
    while (head2->next)
    {
        len2++;
        head2 = head2->next;
    }
    if (head1 != head2)
        return NULL;
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
    if (len1 < len2)
    {
        fast = headB;
        slow = headA;
    }
    int len = abs(len1 - len2);
    while (len--)
    {
        fast = fast->next;
    }
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
            return true;
    }
    return false;
}

struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            struct ListNode* meet = slow;
            while (head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}
